package DataStructure.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和 https://leetcode.cn/problems/3sum/
 * 题目简述：找出一个数组中所有三个不同位置和为0的不重复的三元组
 */
public class ThreeSum {

    public static void main(String[] args) {
        new ThreeSum().threeSum(new int[]{-2,0,1,1,2});
    }

    /**
     * 思路：三指针解法。先将数组升序排序，然后指针i从左向右每遍历一个元素，指针j,k从[i+1, len-1]两端开始向中间扫描，寻找所有包含i的三数之和为0的三元组。j,k移动过程中：
     * 1. 若三数之和为0，则添加结果，然后将j,k向中间移动一步继续寻找解，并略过重复元素，避免加入重复的三元组
     * 2. 若三数之和小于0，则说明j要向右移动，以增大当前和
     * 3. 若三数之和大于0，则说明k要向左移动，以减小当前和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //先排好序
        Arrays.sort(nums);
        //然后从左向右每遍历一个元素i，指针j,k从[i+1, len-1]两端开始向中间扫描，寻找所有包含i的三数之和为0的三元组
        for (int i = 0;i < nums.length;i++) {
            //若nums[i] > 0，则后面的元素都已经大于0了，三数之和不可能为0，直接退出循环
            if (nums[i] > 0) break;
            //重复的i元素得出的三元组肯定是一样的，直接过滤掉
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    //1.若三数之和为0，则添加结果，然后将j,k向中间移动继续寻找解，并略过重复元素，避免加入重复的三元组
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                    k--;
                    while (j < k && nums[k] == nums[k+1]) {
                        k--;
                    }
                } else if (sum < 0) {
                    //2.若三数之和小于0，则说明j要向右移动，以增大三数之和
                    j++;
                } else {
                    //3.若三数之和大于0，则说明k要向左移动，以减小三数之和
                    k--;
                }
            }
        }
        return result;
    }
}
